leetcode经典例题第一题，关于树。

题目描述

Given a binary tree, find its minimum depth.The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

解题思路

解决树的问题，递归肯定是最简单的代码。我们之前练习过求树的最大深度，但是要注意，求最小深度和最大深度是稍微有点不一样的，因为最大深度只需要考虑哪边大即可，即使是单子树（树只有一侧有结点），方式与求双子树的最大深度是一样的。但是对于求最小深度而言，如果出现单子树的情况，那么按照最小深度的定义：根结点到叶子结点的最小距离，那么显然这个最小深度是表示有结点的那一侧。

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int run(TreeNode root) {
        //递归出口条件1
        if(root == null){
            return 0;
        }
        //递归出口条件2
        if(root.left == null && root.right == null){
            return 1;
        }
        //注意点是要考虑是单子树的情况，因为很有可能只有一侧有节点，那么最小深度就是这以一侧
        if(root.left == null){
            return run(root.right)+1;
        }
        if(root.right == null){
            return run(root.left)+1;
        }
        //如果是双子树，则对比树两边谁小即可，与求最大深度一样
        return Math.min(run(root.left),run(root.right))+1;
    }
}